package com.cyc.basic.msb;

/**
 * @Description: 选择排序算法 , 时间复杂度为o(n^2), 空间复杂度为o(1), 稳定性为: 不稳定, 因为相同的值也可能会交换位置
 * @version 1.0
 * @author cyc
 * @date 2021/10/7 20:59
 */
public class SelectionSort {

    public static void main(String[] args) {
        //因为选择排序法, 只有一个数组是占据存储空间的, 其他都是成员变量, 循环一次之后, 就会进行回收, 所以空间复杂度为o(1)
        int[] arr = {5, 3, 6, 8, 1, 7, 9, 4, 2};
        sort(arr);
        print(arr);
    }

    static int[] sort(int[] arr) {

        int minPos;
        for (int i = 0; i < arr.length - 1; i++) {
            //上面这层循环是控制循环次数
            minPos = i;
            for (int j = i + 1; j < arr.length; j++) {
                //下面这个循环是为了比较和交换
                if (arr[minPos] > arr[j]) {
                    //比较minPos位置上的数和j位置上的数谁更大, 如果是minPos更大, 则将minPos赋值为j
                    //总之, minPos在这一次循环里要是最小的值的索引位置
                    minPos = j;
                }
            }
            System.out.println("minPos: " + minPos);
            //交换两个值的位置
            swap(arr, i, minPos);
            System.out.print("经过第" + (i + 1) + "次循环之后, 数组的内容为: ");
            print(arr);
        }
        return arr;
    }

    /**
     * 交换两个位置的值
     * @param arr 数组
     * @param i
     * @param j
     */
    static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    static void print(int[] arr) {
        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k]);
        }
        System.out.println();
    }

}
